package leetcode.tree;

import datastructure.binarytree.TreeNode;

public class LeetCode114 {
    void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        // 拉平左子树
        flatten(root.left);
        // 拉平右子树
        flatten(root.right);
        // 后序位置
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 因为是题目要求是先序顺序，所以当前节点的 next 就是左节点。 题目中，用 right 指针表示 next
        root.right = left;
        // 左指针始终为 null
        root.left = null;
        // 这里p指向 root, 因为  root.right 指向了 left，第一次循环是在找左子节点，所以初始为 root，可以避免 left 为空的情况
        TreeNode p = root;
        // 找当前节点的左子树的最右节点
        while(p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}
